4. Cpp模板(STL)
1 Template(模板简介)
1.1 类模板
1.1.1 类模板的定义和初始化
类模版定义的开头是关键字 template 和一堆尖括号 < ... > 包裹的 Template Parameter List(模板形参列表)，模板形参可以是 Type Parameter (类型形参，关键字 typename)或 Nontype Parameter (非类型形参)，这也是为什么初始化官方的 vector 也需要尖括号，类似于：
#include<vector>
vector<int> vec0; //only declare, vec0 is null
vector<int> vec00(3); //declare a int vector with length of 3, it's elements are default initial value
vector<int> vec1(3, 100); //declare a int vector with length of 3, all of it's elements are 100
创建一个类似于vector的带有模板的类来感受一下：
// typename: 类型形参前的关键词，也可以用class代替
// T: 类型名的占位符，可以是任何名字
// 与标准库的vector不同，这个MyVector是固定大小的
template <typename T, int capacity> class MyVector {
public:
MyVector() : size(0), arr(new T[capacity]) {} // 初始化capacity大小的数组：size=0，arr = new int[5]
~MyVector() { delete[] arr; } // 析构函数
bool isEmpty() { return size == 0; } // 判断是否为空
int getCapacity() { return capacity; }
int getSize() { return size; }
void push(T item) { // 从尾部添加元素
if ( size == capacity ) {
cout << "容量已满！" << endl;
return;
}
arr[size++] = item; // 先放新元素再累加size
}
bool pop(T &item) { // 移除最后元素并返回是否成功(bool)
if ( isEmpty() ) {
return false;
} else {
item = arr[--size]; // 先递减size，再将item赋值为要弹出的元素
return true;
}
}
// 重载下标运算符`[]`，在越界的时候警告并返回第一个元素
T &operator[](int i) {
if ( i >= size || i >= capacity ) {
cout << "下标越界！" << endl;
return arr[0];
}
else { return arr[i]; }
}
private:
T *arr; // 在本例中，类型形参T被初始化为`int`，所以此处创建 `int*`类型的变量`arr`
int size; // 当前元素个数
};
int main() {
MyVector<int, 5> vec; // 容量为5的MyVector容器
cout << "容器的容量为：" << vec.getCapacity() << endl;
cout << "添加元素：" << endl;
for ( int i = 0; i < 3; i++ ) {
vec.push(i);
}
int size = vec.getSize();
for ( int i = 0; i < size; i++ ) {
cout << "容器的第" << i + 1 << "个元素为：" << vec[i] << endl;
}
cout << "移除元素：" << endl;
while ( !vec.isEmpty() ) {
int num;
vec.pop(num);
cout << "移除" << num << endl;
}
return 0;
}
-------------------------------------------------
输出：
容器的容量为：5
添加元素：
容器的第1个元素为：0
容器的第2个元素为：1
容器的第3个元素为：2
移除元素：
移除2
移除1
移除0
上例中，当我们定义 MyVector<int, 5> vec; 时，编译器就知道在编译的时候它需要创建一个新的类定义，其中所有的 T 都要替换成 int，而 capacity 都要替换成 5。编译器所要做的这些替换行为叫作模板实例化（Template Instantiation）。
1.1.2 类模板成员函数的定义分离
当类模板的成员函数的声明在模板外时，语法也与类有所区别：
template<class T> class Interval{ // 区间模板
public:
Interval(T s, T e) : start(s), end(e) {}
void print(); // 类模板的成员函数声明
private:
T start;
T end;
};
template<class T> void Interval<T>::print(){ // 类模板成员函数的定义
cout << "[" << start << ", " << end << "]" << endl;
}
int main() {
Interval<int> int1(3, 4);
cout << "打印int1：" << endl;
int1.print(); // -> [3, 4]
return 0;
}
有两个东西是不能少的：
template关键字和模板形参列表。- 作用域操作符
::前的类名要加上模板形参<T>。这是因为这里的成员函数也是类模板声明的一部分，我们必须标注它的模板特性，不然它就是一个特定版本（比如Interval<int>）的成员函数了。
1.2 函数模板
1.2.1 一般函数和成员函数模板
与类模板类似，函数也可以声明成泛型的形式，包括一般的函数和类成员函数，都可以声明为模板：
#include <iostream>
class Interval{
public:
Interval(int s, int e) : start(s), end(e) {}
int start;
int end;
};
// 重载>使得模板max函数能比较Interval对象
bool operator>(const Interval &lhs, const Interval &rhs) {
if ( lhs.start > rhs.start ) {
return true;
} else if ( lhs.start == rhs.start ) {
return (lhs.end > rhs.end);
} else {
return false;
}
}
// 重载输出操作符使得打印区间方便一些
std::ostream& operator<<ostream& out, const Interval& i{
out << "[" << i.start << ", " << i.end << "]";
return out;
}
template <class T> T max(const T &a, const T &b) { // 函数模板
return (a > b ? a : b);
}
int main() {
int a = 3;
int b = 4;
std::cout << "a和b之间的最大值是：" << max<int>(a, b) << std::endl; // -> 4
Interval int1(1, 2);
Interval int2(1, 3);
std::cout << "int1和int2之间的最大值是：" << max<Interval>(int1, int2) << std::endl; // -> [1, 3]
return 0;
}
调用模板函数时，除了函数名和实参，还要加上模板形参。另外，因为自定义的函数模板 max() 会与 std 命名空间的冲突，所以上例没有使用标准命名空间。
除了一般函数外，函数模板也适用于类成员函数，甚至是类模板的成员函数。也就是说，类模板的成员函数除了类本身的模板形参之外，还有函数自身带的模板形参。
template<typename T> class Vector2D{ // 二维向量
public:
Vector2D(T X, T Y) : x(X), y(Y) {}
// 加法重载函数的右操作数使用成员函数的模板形参类型
template<typename RType> Vector2D add(const RType &rhs);
void print() {
cout << "(" << x << ", " << y << ")" << endl;
}
private:
T x;
T y;
};
// 两个模板形参表都要有
template <typename T> template <typename RType>
Vector2D<T> Vector2D<T>::add(const RType &rhs) {
this->x += rhs;
this->y += rhs;
return *this;
}
int main() {
Vector2D<int> v1(1, 2);
int intNum = 3;
float floatNum = 1.9;
cout << "v1加上intNum的结果为：" << endl;
(v1.add<int>(intNum)).print(); // -> (4, 5)
cout << "v1加上floatNum的结果为：" << endl;
(v1.add<float>(floatNum)).print(); // -> (5, 6)
return 0;
}
1.2.2 默认模板形参
模板形参也可设置默认参数，这与函数声明中的默认参数的用法非常相似。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 二维矩阵
// 默认参数：类型T=int，行m=2，列n=2
template <typename T = int, int m = 2, int n = 2>
class Matrix{
public:
// T()会调用T类型的默认构造函数，如果是int()的话就是初始化为0
Matrix(T val = T()){
row = m;
col = n;
mat = vector<vector<T>>(row, vector<T>(col, val)); // 创建一个row行col列的矩阵，每个元素初始化为val
}
void print() { // 打印矩阵
for ( int i = 0; i < row; i++ ) {
for ( int j = 0; j < col; j++ ) {
cout << mat[i][j] << " ";
}
cout << endl;
}
}
private:
int row;
int col;
vector<vector<T>> mat; // 矩阵
};
int main() {
// 就算使用默认参数也要加上空的尖括号对！
Matrix<> mat1;
cout << "打印mat1：" << endl;
mat1.print();
// 部分使用默认参数
Matrix<string, 3> mat2("零壹快学");
cout << "打印mat2：" << endl;
mat2.print();
Matrix<float, 3, 3> mat3(1.0);
cout << "打印mat3：" << endl;
mat3.print();
return 0;
}
-------------------------------------------------------------------------
输出：
打印mat1：
0 0
0 0
打印mat2：
零壹快学 零壹快学
零壹快学 零壹快学
零壹快学 零壹快学
打印mat3：
1 1 1
1 1 1
1 1 1
1.3 * Template Specialization (模板特化)
1.3.1 模板特化
在 #2.1 一般函数和成员函数模板 的第二个代码示例中，我们实现了add()函数，将Vector2D与某一类型相加，但是函数的实现却决定了这个类型只能是基本类型，并且在两个分量加上相同的数值，或是重载加法能返回特定数值的类。想实现 Vector2D 与 Vector2D 的分量相加，可以用模板特化：
#include <iostream>
using namespace std;
// 模板特化
// Author: 零壹快学
// 二维向量
template<typename T> class Vector2D{
public:
Vector2D(T X, T Y) : x(X), y(Y) {}
// 加法重载函数的右操作数使用成员函数的模板形参类型
template<typename RType> Vector2D add(const RType &rhs);
void print() {
cout << "(" << x << ", " << y << ")" << endl;
}
private:
T x;
T y;
};
// 两个模板形参表都要有
template <typename T> template <typename RType>
Vector2D<T> Vector2D<T>::add(const RType &rhs) {
this->x += rhs;
this->y += rhs;
return *this;
}
// 对于要特化的模板形参表我们只保留空的尖括号对
template <> template <>
Vector2D<int> Vector2D<int>::add(const Vector2D<int> &rhs) {
this->x += rhs.x;
this->y += rhs.y;
return *this;
}
int main() {
Vector2D<int> v1(1, 2);
Vector2D<int> v2(5, 7);
int intNum = 3;
cout << "v1加上intNum的结果为：" << endl;
(v1.add<int>(intNum)).print();
cout << "v1加上v2的结果为：" << endl;
(v1.add<Vector2D<int>>(v2)).print();
return 0;
}
-------------------------------------------------------------
输出：
v1加上intNum的结果为：
(4, 5)
v1加上v2的结果为：
(9, 12)
可以看到，为了防止两个向量相加 v1.add<Vector2D<int>>(v2) 报错 no match for 'operator+=' (operand types are 'int' and 'const Vector2D<int>)，增加了对函数模板的类型参数为 Vector2D<int> 的情况的特殊处理：
// 对于要特化的模板形参表我们只保留空的尖括号对
template <> template <>
Vector2D<int> Vector2D<int>::add(const Vector2D<int> &rhs) {
this->x += rhs.x;
this->y += rhs.y;
return *this;
}
开头的 template <> template <> 让编译器知道这还是一个跟模板有关的函数，形参表为空是因为类型形参已确定，不需要填。
1.3.2 Partial Specialization (偏特化)
我们也可以只对模板的一部分模板形参做特化，而另一部分仍作为动态的参数，也就是偏特化（Partial Specialization）：
#include <iostream>
#include <vector>
using namespace std;
template<typename T, int dim> class MyVec{ // N维向量
public:
MyVec(const vector<T> &Vec): vec(Vec) {
if ( Vec.size() != dim ) {
cout << "传入vector大小不等于dim！" << endl;
}
};
T dot(const MyVec<T, dim> &rhs) { // 点乘
T res(0); // 初始化点乘结果为0
for ( int i = 0; i < dim; i++ ) {
res += (this->vec[i] * rhs.vec[i]);
}
return res;
}
void print() { // 打印向量
cout << "(";
for ( int i = 0; i < dim - 1; i++ ) {
cout << vec[i] << ", ";
}
cout << vec[dim - 1] << ")" << endl;
}
private:
vector<T> vec;
};
// 偏特化二维向量
template<typename T> class MyVec<T, 2>{ // 指定偏特化的参数为dim=2，但这仍然是类模板定义
public:
MyVec(const vector<T> &Vec): vec(Vec) {
if ( Vec.size() != 2 ) {
cout << "传入vector大小不等于dim！" << endl;
}
};
T dot(const MyVec<T, 2> &rhs) { // 点乘
return this->vec[0] * rhs.vec[0] + this->vec[1] * rhs.vec[1];
}
void print() { // 打印向量
cout << "(" << this->vec[0] << ", " << this->vec[1] << ")" << endl;
}
private:
vector<T> vec;
};
int main() {
vector<int> v1 = { 1, 2, 3 };
vector<int> v2 = { 1, 2, 4 };
MyVec<int, 3> v3_1(v1);
MyVec<int, 3> v3_2(v2);
cout << "v3_1与v3_2点乘的结果为：" << v3_1.dot(v3_2) << endl; // -> 17
vector<int> v3 = { 1, 2 };
vector<int> v4 = { 3, 4 };
// 能使用特化版本的时候编译器就会尽量使用特化版本的类定义
MyVec<int, 2> v2_1(v3);
MyVec<int, 2> v2_2(v4);
cout << "v2_1与v2_2点乘的结果为：" << v2_1.dot(v2_2) << endl; // -> 11
return 0;
}
在这个偏特化的二维向量的类定义中，我们依然保持 T 为未特化的状态，而将使用 dim 的地方都改成 2。这样之后不管我们定义了 MyVec<int, 2> 还是 MyVec<float, 2>，编译器都会自动生成相应的完全特化的类定义。
1.4 * 多维 vector
2 STL (标准模板库)
Info
C++标准库的一个强大之处就是它包含了各种各样的容器和算法，并且都是泛型（Generic）的，可以实现泛型编程（Generic Programming）。所谓泛型编程，就是在编程时不需要考虑具体数据类型，不需要寻找并使用类型与当前变量匹配的算法，而算法使用的数据结构，也就是容器，也不需要根据数据类型重复实现不同版本。
C++标准库中，容器和算法所在的标准库子集又叫标准模板库（Standard Template Library），简称STL。它之所以比标准库多了“模板”两字，是因为模板就是C++中实现泛型编程的重要工具。vector可以声明为不同元素类型，就是利用了模板。
2.1 容器
STL 的容器分为顺序容器和关联容器。顺序容器按元素的位置顺序存储访问；关联容器通过键来查找对应的元素。容器有许多共享的函数，如 insert()、assign() 等等，关联容器与顺序容器也会共享除了push()、pop()等以外的大多数操作。
2.1.1 Itertor (迭代器)
无论我们使用的是哪一种容器，都可以用迭代器一刀切地进行遍历，而不需要关心遍历具体是怎么实现的。
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec;
cout << "请输入5个vector元素：" << endl;
for ( int i = 0; i < 5; i++ ) {
int num = 0;
cin >> num;
vec.push_back(num);
}
cout << "遍历vector：" << endl;
// 定义特定类型的迭代器，并初始化为指向容器第一个元素的迭代器begin()
vector<int>::iterator it = vec.begin();
// end()返回指向容器最后一个元素后一个元素的迭代器
for ( ; it != vec.end(); it++ ) {
// 把迭代器看做指针，解引用
cout << *it << endl;
}
return 0;
}
-----------------------------------------------------
输出：
请输入5个vector元素：
5 4 3 2 1
遍历vector：
5
4
3
2
1
迭代器是在每个容器类定义中声明的，因此定义时需在关键字 iterator 前加上具体的容器名(上例为 vector<int>)和作用域操作符 ::，并初始化/赋值为指向容器的第一个元素和最后一个元素之后的元素的迭代器(begin() 和 end())。
也可以使用反向迭代器 reverse_iterator 和 rbegin(), rend() 进行反向遍历：
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> vec;
cout << "请输入5个vector元素：" << endl;
for ( int i = 0; i < 5; i++ ) {
int num = 0;
cin >> num;
vec.push_back(num);
}
cout << "使用反向迭代器遍历vector：" << endl;
vector<int>::reverse_iterator rev_it = vec.rbegin();
// rbegin()指向的是容器的最后一个元素，rend()指向的是第一个元素之前的元素
for ( ; rev_it != vec.rend(); rev_it++ ) {
cout << *rev_it << endl;
}
return 0;
}
2.1.2 容器元素的条件
容器元素的类型是比较随意的，可以是基本类型，也可以是自定义类型。作为容器元素的类型需要满足两个基本条件：(1)支持赋值操作符; (2)支持复制操作。也就是不能将复制构造函数和赋值操作符重载为私有成员，因为容器的许多操作都涉及复制控制。
2.1.3 一些公共的操作
以vector为例子介绍容器的一些共通的操作。
清空和判断是否为空 clear-empty-size
vector<int> vec;
vec.clear();
vec.empty();
vec.size();
添加和删除元素
insert-erase
vector<int> vec;
vector<int> vec;
// 初始化vector
for ( int i = 0; i < 5; i++ ) {
vec.push_back(i);
}
// 插入一个3到第二个元素前面
vec.insert(vec.begin() + 1, 3); // vec = 0 3 1 2 3 4
// 将刚才插入的3移除
vec.erase(vec.begin() + 1); // vec = 0 1 2 3 4
// 插入三个3到第五个元素前面
vec.insert(vec.begin() + 4, 3, 3); // vec = 0 1 2 3 3 3 3 4
// 将刚才插入的三个3移除，vec.end() - 1虽然指向最后一个元素，但erase只删除到前一个元素，即末尾的4不被删除
vec.erase(vec.begin() + 4, vec.end() - 1); // vec = 0 1 2 3 4
erase-remove惯用法（Erase-Remove Idiom）
#include <algorithm> // 包含remove()的头文件，大多数STL泛型算法都定义此处
// 初始化vector
vector<int> vec;
for ( int i = 0; i < 10; i++ ) {
// 除2余1的数，也就是奇数
if ( i % 2 == 1 ) {
vec.push_back(1);
} else {
vec.push_back(i);
}
} // vec = 0 1 2 1 4 1 6 1 8 1
// 将vec中的1移除后把后面的元素调整到前面来
vector<int>::iterator firstToErase = remove(vec.begin(), vec.end(), 1); // vec = 0 2 4 6 8 1 6 1 8 1
// 将vec中多余的元素删除
vec.erase(firstToErase, vec.end()); // vec = 0 2 4 6 8
// 这里为了打印中间结果将两个函数拆开，实际应该写成：
// vec.erase(remove(vec.begin(), vec.end(), 1), vec.end());
return 0;
留意 remove() 函数的说明：
Returns:
An iterator designating the end of the resulting sequence. 也就是指向0 2 4 6 8中的元素8的迭代器。
All elements equal to __value are removed from the range[__first,__last). 也就是0 1 2 1 4 1 6 1 8 1中的1被删除。
remove() is stable, so the relative order of elements that are not removed is unchanged.
Elements between the end of the resulting sequence and __last are still present, but their value is unspecified. 也就是从0 2 4 6 8往后的1 6 1 8 1会被保留。因此需要用vec.erase(firstToErase, vec.end())删除8往后的元素。
交换元素 swap
vec1.swap(vec2); // 交换所有元素（指针层面的操作）
2.2 vector
在这里补充顺序容器 vector 的其他常用操作和特性。
2.2.1 assign
vector以及其他的顺序容器都支持assign操作。assign操作可以将容器中的现有内容删除，并用其他容器中一定范围内的元素填充，或是填充一定数目的相同元素。
vector<int> vec;
vector<int> vecSrc;
// 初始化
for ( int i = 0; i < 5; i++ ) {
vecSrc.push_back(i);
} // vecSrc = {0, 1, 2, 3, 4}
// 将vecSrc的值assign给vec：
vec.assign(vecSrc.begin(), vecSrc.end()); // vec = {0, 1, 2, 3, 4}
// 添加两个元素
vec.push_back(6);
vec.push_back(6); // vec = {0, 1, 2, 3, 4, 6, 6}
// 将vecSrc的部分值assign给vec
vec.assign(vecSrc.begin() + 1, vecSrc.end() - 1); // vec = {1, 2, 3}
// 将五个6assign给vec
vec.assign(5, 6); // vec = {6, 6, 6, 6, 6}
2.2.2 resize
resize会改变容器的大小，并截掉多余的部分或填补多出的部分。
vector<int> vec;
// 初始化vec
for ( int i = 0; i < 5; i++ ) {
vec.push_back(i);
} // vec = {0, 1, 2, 3, 4}
// 将vec的大小resize成3
// 在新的size比原来小的情况下，指定填充的0也并没有用
vec.resize(3, 0); // vec = {0, 1, 2}
// 将vec的大小resize成6
// 在新的size比原来大的情况下，指定填充的0就有用了
vec.resize(6, 0); // vec = {0, 1, 2, 0, 0, 0}
迭代器失效
std::vector::erase(it) 会使被删除元素之后（包括被删除元素）的所有元素的迭代器失效，对一个已失效的迭代器执行 it++ 是一种未定义行为（Undefined Behavior），会导致程序崩溃/产生不可预测的结果（跳过本应检查的下一个元素）：
#include <iostream>
#include <vector>
using namespace std;
// 迭代器失效
void print(const vector<int> &vec) {
for ( int i = 0; i < vec.size(); i++ ) {
cout << vec[i] << " ";
}
cout << endl;
}
int main() {
vector<int> vec;
cout << "初始化vec：" << endl;
for ( int i = 0; i < 10; i++ ) {
vec.push_back(i);
}
print(vec); // vec = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
cout << "移除奇数元素：" << endl;
int cnt = 0;
vector<int>::iterator it = vec.begin();
for ( ; it != vec.end(); cnt++, it++ ) {
cout << "cnt = " << cnt << endl;
cout << "it = " << *it << endl;
if ( cnt % 2 == 1 ) {
vec.erase(it);
}
print(vec);
}
return 0;
}
--------------------------------------------------
输出：
初始化vec：
0 1 2 3 4 5 6 7 8 9
移除奇数元素：
cnt = 0
it = 0
0 1 2 3 4 5 6 7 8 9
cnt = 1
it = 1
0 2 3 4 5 6 7 8 9
cnt = 2
it = 3 // 迭代器指向了“下一个元素”，而不是指向 2
0 2 3 4 5 6 7 8 9
cnt = 3
it = 4
0 2 3 5 6 7 8 9
cnt = 4
it = 6
0 2 3 5 6 7 8 9
cnt = 5
it = 7
0 2 3 5 6 8 9
cnt = 6
it = 9
0 2 3 5 6 8 9
该例中，对迭代器的正确处理如下：
// 初始化 vec
std::vector<int> vec;
for (int i = 0; i < 10; i++) {
vec.push_back(i);
} // vec = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
for (auto it = vec.begin(); it != vec.end(); /* 此处的迭代器更新移至循环体内部 */) {
if (*it % 2 != 0) { // 判断元素值是否为奇数
// 如果删除，it 被更新为指向下一个有效元素
it = vec.erase(it);
std::cout << "删除奇数元素: " << *(it - 1) << "，当前 vec: ";
print(vec);
} else {
// 如果不删除，才安全地移动到下一个元素
it++;
}
} // 最终 vec (只剩偶数): ";
print(vec); // 最终 vec = {0, 2, 4, 6, 8}
-------------------------------------------------------
输出：
删除奇数元素: 0，当前 vec: 0 2 3 4 5 6 7 8 9
删除奇数元素: 2，当前 vec: 0 2 4 5 6 7 8 9
删除奇数元素: 4，当前 vec: 0 2 4 6 7 8 9
删除奇数元素: 6，当前 vec: 0 2 4 6 8 9
删除奇数元素: 8，当前 vec: 0 2 4 6 8
0 2 4 6 8
2.2.3 一些实例
用 vector 判断 anagram
anagram：相同字母异序词，易位构词，变位词
数组的元素都是排列在一起的，所以随机访问某一个元素只需要首个元素的地址加上偏移量就能够定位到。而在删除数组中元素的时候，我们需要将被删除元素后面的所有元素往前移动一格，不然数组会有空隙（erase() 自动完成这一点，但会有性能损耗）。因此，vector 适用于元素随机访问多但添加、删除中间元素少的程序。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool isAnagram(string s, string t) {
unsigned lenS = s.length();
if ( lenS != t.length() ) return false; // anagram单词长度必然是相等的
// 用vector记录每个字母出现的频次
vector<int> freqTab(26, 0);
for (unsigned i = 0; i < lenS; i++ ) {
// 使用 s[i] - 'a' 得到字母对应的数组位置
freqTab[s[i] - 'a']++;
freqTab[t[i] - 'a']--;
}
// 看看是不是每个字母的相差频次都为0
for ( unsigned i = 0; i < 26; i++ ) {
if ( freqTab[i] != 0 ) {
return false;
}
}
return true;
}
int main() {
string word1 = "";
string word2 = "";
cout <<"请输入两个单词，用回车间隔："<< endl;
cin >> word1;
cin >> word2;
if ( isAnagram(word1, word2) ) {cout <<"两个单词是anagram！"<< endl;}
else {cout <<"两个单词不是anagram！"<< endl;}
return 0;
}
--------------------------------------
输出：
请输入两个单词，用回车间隔：
listen
silent
两个单词是anagram！
虽然 vector 在中间添加和删除元素的效率很低，但是在末尾添加和删除元素还是很直观有效的，我们可以用现成的 push_back() 和 pop_back() 函数，还可以把 vector 当作栈来使用。栈(Stack)是一种满足只从线性数据集合一端添加和删除元素的数据结构。
判断有效括号序列
有效括号：左右括号是一一匹配的
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 判断有效括号，可以把 `vector` 当作栈来使用
// ()()或者(())这样的括号对是有效的
// 而(()或者（()这样的括号对是无效的
bool isValid(string s) {
vector<char> stack;
for ( int i = 0; i < s.length(); i++ ) {
if ( s[i] == '(' ) {
// 左括号无条件进栈
stack.push_back(s[i]);
} else if (!stack.empty() && ((s[i] == ')') && (stack.back() == '(')) ) {
// 右括号抵消一个栈中的左括号
stack.pop_back();
} else {
// 非括号的无效字符或者右括号找不到对应左括号的情况
return false;
}
}
// 最后所有括号应该都被抵消，栈为空
return stack.empty();
}
int main() {
string parenSeq = "";
cout << "请输入一个由任意“(”和“)”组成的括号序列：" << endl;
cin >> parenSeq;
if ( isValid(parenSeq) ) {
cout << "有效括号序列！" << endl;
} else {
cout << "无效括号序列！" << endl;
}
return 0;
}
------------------------------------------------
输出：
请输入一个由任意“(”和“)”组成的括号序列：
()()((()))((((((()))))))
有效括号序列！
2.3 list
顺序容器 list 与 vector 的不同之处在于 list 可以快速地添加和删除元素。list 的底层是由双链表(Double Linked List)实现的。链表的原理可见 C 语言或参考书，不赘述。注意，由于底层设计的不同，链表和数组 array 有着较大的区别：
其中数组有以下特点：
1．数组是一块连续的区域。
2．数组需要预留空间，可能会有空间没有数据或者数据不够放的情况。
3．插入和删除效率低，需要移动后继的元素。
4．随机访问效率高，因为每个元素地址都是已知的。
而链表则有以下特点：
1．链表的每个节点都不需要连续，可以放在任何地方。
2．不用预留空间，数据可随意增删。
3．每个节点都存着下个节点的地址。
4．访问需要顺着一个个节点找，不支持随机访问。
2.3.1 常用操作
先用一个示例将 list 的常见操作都介绍一遍。